package LeetCodeTest;

public class Solution {
    /**
     * 模拟，贪心
     * 解题思路：定义一个five用于记录5元的钞票有多少个，定义一个ten用于记录10元的钞票有多少张
     * 每当收钱时对应的钞票++，找零时对应的钞票--
     * 找零的金额为收取的钞票减去5元
     */
    boolean lemonadeChange0(int[] bills){
        int five = 0;
        int ten  = 0;
        for (int i = 0; i < bills.length; i++) {
            if (bills[i]==5)five++;
            if (bills[i]==10)ten++;
            Integer change = bills[i] - 5;
            while (change!=0){
                if (change>=10){
                    change-=10;
                    ten--;
                }
                if (change.equals(5)){
                    change-=5;
                    five--;
                }
            }
            if (ten<0 || five<0)return false;
        }
        return true;
    }
    boolean lemonadeChange1(int[] bills) {
        int five = 0;
        int ten = 0;
        for (int bill : bills) {
            if (bill == 5){
                five++;
            } else if (bill == 10){
                if (five == 0){
                    return false;
                }
                five--;
                ten++;
            }else {
                if (five > 0 && ten > 0){
                    five--;
                    ten--;
                }else if (five >= 3){
                    five-=3;
                }else {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 深度优先搜索
     * 解题思路：通过不断递归，将数组的中间的数据放入当前treeNode的根中
     * 左边的放到左子树，右边的放到右子树
     * @param nums 用nums这个数组生成二叉排序数
     * @return n   返回一个深度尽可能小的二叉搜索树
     */
//    public Node sortedArrayToBST(int[] nums) {
//        if(nums.length==0) return null;
//        Node n ;
//        n = new Node(nums[nums.length/2]);
//        n.left = sortedArrayToBST(Arrays.copyOfRange(nums,0,nums.length/2));
//        n.right = sortedArrayToBST(Arrays.copyOfRange(nums,nums.length/2+1,nums.length));
//        return n;
//    }
}
